package divideAndConquer;

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * 为运算表达式设计优先级
 * 给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
 */
public class P241 {

    Pattern pattern = Pattern.compile("\\d+");

    public List<Integer> diffWaysToCompute(String expression) {
        if (expression == null) {
            return new ArrayList<>(0);
        }
        List<Integer> result = new ArrayList<>();
        // 查看是否有符号
        Matcher matcher = pattern.matcher(expression);
        if (matcher.find() && matcher.group().length() == expression.length()) {//全是数字
            int num = 0;
            for (char c : expression.toCharArray()) {
                num = num * 10 + Integer.valueOf("" + c);
            }
            result.add(num);
            return result;
        } else {//包含运算符
            char[] items = expression.toCharArray();
            for (int i = 0; i < items.length; i++) {
                if (isOpt(items[i])) {
                    List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                    List<Integer> right = diffWaysToCompute(expression.substring(i + 1, items.length));
                    execute(left, items[i], right, result);
                    result.sort((a, b) -> {
                        return a - b;
                    });
                }
            }
            return result;
        }
    }

    private void execute(List<Integer> left, char opt, List<Integer> right, List<Integer> result) {
        switch (opt) {
            case '+': {
                for (int a : left) {
                    for (int b : right) {
                        result.add(a + b);
                    }
                }
            }
            break;
            case '-': {
                for (int a : left) {
                    for (int b : right) {
                        result.add(a - b);
                    }
                }
            }
            break;
            case '*': {
                for (int a : left) {
                    for (int b : right) {
                        result.add(a * b);
                    }
                }
            }
            break;
            default:
                System.err.println("不支持的运算符");
        }

    }

    private boolean isOpt(char c) {
        if (c == '+' || c == '-' || c == '*') {
            return true;
        } else {
            return false;
        }
    }


    //-----动态规划--------------------------------------------------
    public List<Integer> dp(String expression) {
        // 1. 提取数字
        List<Integer> nums = new ArrayList<>();
        Matcher matcher = Pattern.compile("\\d+").matcher(expression);
        while (matcher.find()) {
            nums.add(Integer.valueOf(matcher.group()));
        }
        // 2. 提取符号
        List<String> opts = new ArrayList<>();
        matcher = Pattern.compile("[\\+\\-\\*]").matcher(expression);
        while (matcher.find()) {
            opts.add(matcher.group());
        }

        return null;
    }


    public static void main(String[] args) {
        //System.out.println(new P241().diffWaysToCompute("2*3-4*5"));
        Matcher matcher = Pattern.compile("\\d+").matcher("1+2");
        while (matcher.find()) {
            System.out.println(matcher.group());
        }
    }
}
